#ifndef DATASTRUCTURE_CHAINLIST_H
#define DATASTRUCTURE_CHAINLIST_H
#include <iostream>
using namespace std;

/**
 * 链式列表（单链表）实现
 * 
 * 链表的优点：
 * 1. 不需要预先分配固定大小的内存空间
 * 2. 插入和删除操作效率高（O(1)时间复杂度，不考虑查找过程）
 * 3. 不需要像数组一样在插入元素时移动大量数据
 * 4. 动态扩展大小，不会浪费内存空间
 * 
 * 链表的缺点：
 * 1. 不能随机访问元素，访问特定位置需要从头开始遍历（O(n)时间复杂度）
 * 2. 每个节点需要额外的内存空间存储指针
 * 3. 对于频繁的随机访问操作，效率低于数组
 * 4. 内存利用率较低，因为需要为每个节点分配内存
 */
template <typename T>
class ChainList {
private:
    /**
     * 链表节点结构体定义
     * 包含数据域和指向下一个节点的指针
     */
    struct ListNode {
        T data;        // 节点存储的数据
        ListNode* next; // 指向下一个节点的指针
    };
    ListNode* head;  // 链表头节点指针
    size_t size;     // 链表当前元素个数

public:
    /**
     * 默认构造函数
     * 初始化空链表
     */
    ChainList(){
        head = nullptr;  // 头节点初始化为空
        size = 0;        // 初始大小为0
    }

    /**
     * 带参构造函数
     * 创建一个包含指定值的单节点链表
     * @param val 初始节点的值
     */
    ChainList(T val){
        head = new ListNode; // 创建新节点作为头节点
        head->data = val;    // 设置节点数据
        head->next = nullptr; // 初始时无后继节点
        size = 1;            // 初始大小为1
    }

    /**
     * 析构函数
     * 释放链表所有节点的内存
     */
    ~ChainList(){
        ListNode* temp;      // 临时指针，用于保存下一个要处理的节点
        while(head != nullptr){
            temp = head->next; // 保存下一个节点
            delete head;       // 释放当前节点内存
            head = temp;       // 移动到下一个节点
        }
        // head已经为nullptr，不需要再释放
    }

    /**
     * 在链表头部添加新元素
     * @param val 要添加的元素值
     */
    void push_front(const T& val);

    /**
     * 在链表尾部添加新元素
     * @param val 要添加的元素值
     */
    void push_back(const T& val);

    /**
     * 删除链表中第一个值为val的元素
     * @param val 要删除的元素值
     * @return 成功删除返回true，未找到要删除的元素返回false
     */
    bool remove(const T& val);

    /**
     * 显示链表中的所有元素
     */
    void show();

    /**
     * 获取链表当前的元素个数
     * @return 链表的大小
     */
    size_t getSize();
};

/**
 * 在链表头部添加新元素的实现
 * 时间复杂度：O(1)
 * @param val 要添加的元素值
 */
template<typename T>
void ChainList<T>::push_front(const T &val) {
    ListNode* temp = new ListNode; // 创建新节点
    temp->data = val;              // 设置节点数据
    temp->next = head;             // 新节点指向当前头节点
    head = temp;                   // 更新头节点指针
    size++;                        // 更新链表大小
}

/**
 * 在链表尾部添加新元素的实现
 * 时间复杂度：O(n)，需要遍历到链表尾部
 * @param val 要添加的元素值
 */
template<typename T>
void ChainList<T>::push_back(const T &val) {
    // 处理空链表情况
    if(head == nullptr){
        head = new ListNode;       // 创建新节点作为头节点
        head->data = val;          // 设置节点数据
        head->next = nullptr;      // 尾节点next为nullptr
        size = 1;                  // 更新链表大小
        return;
    }

    // 创建新节点
    ListNode* temp = new ListNode;
    temp->data = val;
    temp->next = nullptr;

    // 遍历到链表尾部
    ListNode* p = head;
    while(p->next != nullptr){
        p = p->next;
    }

    // 在尾部添加新节点
    p->next = temp;
    size++;                        // 更新链表大小
}

/**
 * 删除链表中第一个值为val的元素的实现
 * 时间复杂度：O(n)，最坏情况需要遍历整个链表
 * @param val 要删除的元素值
 * @return 成功删除返回true，未找到要删除的元素返回false
 */
template<typename T>
bool ChainList<T>::remove(const T &val) {
    // 处理空链表的情况
    if(head == nullptr) {
        return false;
    }

    // 处理要删除的是头节点的情况
    if(head->data == val) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
        size--;  // 更新链表大小
        return true;
    }

    // 处理其他情况：查找要删除的节点
    ListNode* p = head;       // 当前遍历到的节点
    ListNode* q = head;       // 当前节点的前驱节点
    while(p != nullptr && p->data != val){
        q = p;
        p = p->next;
    }

    // 没有找到要删除的元素
    if(p == nullptr){
        return false;
    }

    // 删除找到的元素
    q->next = p->next;
    delete p;
    size--;  // 更新链表大小
    return true;
}

/**
 * 显示链表中所有元素的实现
 */
template<typename T>
void ChainList<T>::show() {
    cout << "ChainList: " << endl;  // 输出链表标题
    ListNode* p = head;             // 从头部开始遍历
    while(p != nullptr){
        cout << "\t" << p->data << endl;  // 输出当前节点数据
        p = p->next;                      // 移动到下一个节点
    }
    cout << "Size: " << size << endl;  // 输出链表大小
}

/**
 * 获取链表当前元素个数的实现
 * @return 链表的大小
 */
template<typename T>
size_t ChainList<T>::getSize() {
    return size;
}

#endif //DATASTRUCTURE_CHAINLIST_H